package com.cb2.algorithm.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/validate-binary-search-tree/">验证二叉搜索树(Validate Binary Search Tree)</a>
 * <p>给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。有效 二叉搜索树定义如下：
 * <ul>
 *     <li>节点的左子树只包含 小于 当前节点的数。</li>
 *     <li>节点的右子树只包含 大于 当前节点的数。</li>
 *     <li>所有左子树和右子树自身必须也是二叉搜索树。</li>
 * </ul>
 * </p>
 * <p>
 *     <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：root = [2,1,3]
 *      输出：true
 *
 *  示例 2：
 *      输入：root = [5,1,4,null,null,3,6]
 *      输出：false
 *      解释：根节点的值是 5 ，但是右子节点的值是 4 。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 * <li>树中节点数目范围在[1, 10^4] 内</li>
 * <li>-2^31 <= Node.val <= 2^31 - 1</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/10 16:13
 */
public class LC0098ValidateBinarySearchTree_M {
    static class Solution {
        public boolean isValidBST(TreeNode root) {
            //return isValidBSTByIterator(root);
            return isValidBSTByRecursion(root);
        }

        /**
         * 前序遍历
         */
        private boolean isValidBSTByIterator(TreeNode node) {
            long prev_node_val = Long.MIN_VALUE;
            Deque<TreeNode> stack = new LinkedList<>();
            while (node != null || !stack.isEmpty()) {
                while (node != null) {
                    stack.addFirst(node);
                    node = node.left;
                }
                TreeNode currNode = stack.removeFirst();
                if (currNode.val <= prev_node_val) {
                    return false;
                }
                prev_node_val = currNode.val;
                node = currNode.right;
            }
            return true;
        }

        private boolean isValidBSTByRecursion(TreeNode node) {
            return isValidBSTByRecursion(node, Long.MIN_VALUE, Long.MAX_VALUE);
        }

        private boolean isValidBSTByRecursion(TreeNode node, long lower, long upper) {
            if (node == null) {
                return true;
            }
            if (node.val <= lower || node.val >= upper) {
                return false;
            }
            return isValidBSTByRecursion(node.left, lower, node.val) && isValidBSTByRecursion(node.right, node.val, upper);
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(2);
        root1.left = new TreeNode(1);
        root1.right = new TreeNode(3);

        TreeNode root2 = new TreeNode(5);
        root2.left = new TreeNode(1);
        root2.right = new TreeNode(4);
        root2.right.left = new TreeNode(3);
        root2.right.right = new TreeNode(6);

        Solution solution = new Solution();
        System.out.println(solution.isValidBST(root1));
        System.out.println(solution.isValidBST(root2));
    }
}